package com.github.wings27.interview.Problem;

/**
 * Project Name: CIP
 * Date Created: 2014/02/07 22:27
 *
 * @author Wings
 */
public class MaxSubseqSum {
    public static void main(String[] args) {
        int[] a = {-16, -2, -3, -10, -4, -7, -2, -5};
        System.out.println(maxSubseq1(a));
        System.out.println(maxSubseq2(a));
    }

    static int maxSubseq1(int[] array) {
        return maxSubseq1(array, 0, array.length - 1);
    }

    static int maxSubseq1(int[] array, int l, int u) {
        // O(n*logn)
        if (l > u) {
            return 0;
        }
        if (l == u) {
            return array[l];
        }
        int m = (l + u) / 2;

        int sum = 0;
        int lMax = Integer.MIN_VALUE;
        for (int i = m; i >= l; i--) {
            sum += array[i];
            if (sum > lMax) {
                lMax = sum;
            }
        }

        sum = 0;
        int rMax = Integer.MIN_VALUE;
        for (int i = m + 1; i <= u; i++) {
            sum += array[i];
            if (sum > rMax) {
                rMax = sum;
            }
        }

        return max3(lMax + rMax, maxSubseq1(array, l, m), maxSubseq1(array, m + 1, u));
    }

    static int max3(int a, int b, int c) {
        if (b < a) b = a;
        if (c < b) c = b;
        return c;
    }

    static int maxSubseq2(int[] array) {
        // O(n)
        int sumSoFar = array[0];
        int result = sumSoFar;
        for (int i = 1; i < array.length; i++) {
            if (sumSoFar < 0) {
                sumSoFar = array[i];
            } else {
                sumSoFar += array[i];
            }
            if (sumSoFar > result) {
                result = sumSoFar;
            }
        }
        return result;
    }
}
